package com.base.dp;

import java.util.ArrayList;
import java.util.List;

public class GenerateTrees {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        GenerateTrees generateTrees = new GenerateTrees();
        System.out.println(generateTrees.generateTrees(3));
    }

    /**
     * 以下是生成所有不同二叉搜索树的递归算法思路：
     * <p>
     * 基本情况：如果开始或结束索引超出范围（即 start > end），则返回一个空列表，表示没有树可以生成。
     * 递归构建：对于每个数字 i（从 start 到 end），执行以下操作：
     * 将 i 作为根节点。
     * 递归地生成左子树，使用值 start 到 i-1。
     * 递归地生成右子树，使用值 i+1 到 end。
     * 将所有可能的左子树和右子树组合与根节点 i 组合。
     * 合并结果：对于每个 i，将所有可能的左子树和右子树组合与根节点 i 组合并添加到结果列表中。
     *
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }



    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> list = new ArrayList<>();
        //退出条件
        if (start > end) {
            list.add(null);
            return list;
        }
        for (int i = start; i <= end; i++) {
            //遍历每一个根节点,生成每个根节点的左子树，右子树
            List<TreeNode> left = generateTrees(start, i - 1);
            List<TreeNode> right = generateTrees(i + 1, end);
            //左右不相关，需要乘起来
            for (TreeNode leftNode : left) {
                for (TreeNode rightNode : right) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftNode;
                    treeNode.right = rightNode;
                    list.add(treeNode);
                }
            }
        }
        return list;
    }
}
